package leetcode_day._2021._202111;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/20 11:36
 * 最长和谐子序列
 * 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
 * 现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
 * 数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
 * 算法：排序 + 双指针 + 滑动窗口
 * 因为子序列可以是不连续的，所以可以将数组排序后去找
 * 时间复杂度：排序的复杂度为 O(nlogn)，通过双指针实现的滑动窗口复杂度为 O(n)。整体复杂度为 O(nlogn)
 * 空间复杂度：O(logn)
 * --------------------------------------------------------------------------------
 * 算法：哈希表
 * 时间复杂度和空间复杂度都是o(n)
 */
public class _20_594 {
    public static void main(String[] args) {
        System.out.println(findLHS(new int[]{1, 3, 2, 2, 5, 2, 3, 7}));
    }

    public static int findLHS(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int l = 0, r = 0; r < nums.length; ++r) {
            while (l < r && nums[r] - nums[l] > 1) ++l;
            if (nums[r] - nums[l] == 1) ans = Math.max(ans, r - l + 1);
            // 当 retain 小于 1 时，因为是排序过的，所以 retain 肯定为 0，表示元素相等，只需要 r 往后移
        }
        return ans;
    }

    /**
     * 因为相差为 1，那么说明是相邻的两个数
     * 只要计算两个相邻的数的个数即可
     * @param nums
     * @return
     */
    public static int findLHS_hash(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(16);
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        int ans = 0;
        for (int num : nums)
            if (map.containsKey(num - 1)) ans = Math.max(ans, map.get(num) + map.get(num - 1));
        return ans;
    }

}
